Embodiments of the present invention relate to the field of computer systems. In particular, embodiments of the present invention relate to a method, system, and computer program product for reducing the time taken to execute instructions in a software loop.
A compiler is a program that reads a source code (in a source language) and translates it into a target code (in a machine language). The compiler, while forming the target code, formulates an intermediate code (in a machine-independent form). For example, a compiler for FORTRAN translates a high-level source code in the FORTRAN programming language into a target code in machine language, which can be executed by a computer processor. In addition, the compiler for FORTRAN, while forming the target code, formulates an intermediate code. Machine-independent optimizations may be carried out on the intermediate code.
Conventional compilers include three stages—a front end, a middle end, and a back end. The front end translates the source code into the intermediate code. The middle end optimizes the intermediate code, using machine independent optimizations. The back end generates the target code, which is optimized by using machine-dependent optimizations.
Optimizing the intermediate code refers to the transformation of the intermediate code into an alternate functionally equivalent code that has reduced execution time. The time taken to execute the source code depends on a number of factors. These factors include the number of instructions required to execute the source code, the average number of processor cycles required to execute an instruction, and the cycle time of the processor.
Various methods have been used to optimize intermediate codes in the machine-independent form in the compiler. These methods facilitate the reduction of the height of the instructions in a basic block of a software loop. The basic block is a straight-line piece of code without any jumps in the middle of the block.
Software loops are usually the places where the bulk of the execution time is spent in a program. Therefore, speeding up the execution of these loops can save execution time. Some loops are resource-bound, i.e., they are bound by the number of issue and instructions slots available for their instructions. However, many other loops are recurrence-bound, i.e., they are limited in performance by the availability of results from an earlier iteration. Traditionally, reassociation is used to reduce the height of a computation, i.e., it is used to re-order the computation in a basic block, so that a given instruction can be executed faster than before. Such techniques, while they are useful for speeding up computation in acyclic regions, may not always speed up the execution of loops. What is important in speeding up recurrence-bound loops is to reduce their critical recurrence cycles, and not so much to reduce their heights in the basic blocks.